class Solution1 {
    public int lastStoneWeightII(int[] stones) {
         int len = stones.length ;
         int sum = 0 ; 
         for(int x : stones){
            sum += x ;
         }
         int target = sum /2 ;
         int[] dp = new int[target+1] ;
         for(int i=0 ;  i< len ; i ++){
            for(int j=target ; j >=1 ; j--){
                if(j>=stones[i]){
                    dp[j] = Math.max(dp[j] , stones[i]+dp[j-stones[i]]) ; 
                }
            }
         }       
     int b = sum - dp[target] ; 
     return dp[target]>b?dp[target]-b : b-dp[target] ; 

    }
}